package com.cat.binaryTree;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/all-elements-in-two-binary-search-trees/
 * @create 2025/9/15 20:40
 * @since JDK17
 */

public class Solution47 {
    void f(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        f(root.left, list);
        list.add(root.val);
        f(root.right, list);
    }
    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        List<Integer> list1 = new ArrayList<>(), list2 = new ArrayList<>();
        f(root1, list1);
        f(root2, list2);
        List<Integer> ans = new ArrayList<>();
        int i, j, n = list1.size(), m = list2.size();
        for (i = j = 0; i < n && j < m; ) {
            if (list1.get(i) < list2.get(j)) {
                ans.add(list1.get(i++));
            } else {
                ans.add(list2.get(j++));
            }
        }
        while (i < n) {
            ans.add(list1.get(i++));
        }
        while (j < m) {
            ans.add(list2.get(j++));
        }
        return ans;
    }
}
